public class Leetcode {
}

//leetcode:704:二分查找
class Solution1 {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left <= right){
            int mid = left+(right-left)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else if(nums[mid] > target){
                right = mid-1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

//leetcode:34:在排序数组中查找元素的第一个和最后一个位置
class Solution2 {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0]=ret[1]=-1;
        //处理边界情况
        if(nums.length == 0){
            return ret;
        }
        //二分左端点
        int left = 0,right = nums.length-1;
        while(left < right){
            int mid = left+(right-left)/2;//找左端点，取中间点的方式，防止死循环
            //找左端点，让left跳出小于target的区间，即跳出左端点的左边，达到左端点
            if(nums[mid] < target){
                left = mid+1;
            }else{//让right不断向前移动达到大于等于target区间的最左边，即左端点，让right等于左端点
                right = mid;
            }
        }
        //判断是否有结果
        if(nums[left] != target){
            return ret;
        }else{
            ret[0] = right;//有结果就让ret[0]处赋值为right，即左端点坐标
        }
        //二分右端点
        left = 0;right = nums.length-1;//注意要重新定义left和rigth的位置
        while(left < right){
            int mid = left+(right-left+1)/2;//找右端点，取中间点的方式，防止死循环
            //找右端点，让right跳出大于target的区间，即跳出右端点的右边，达到右端点
            if(nums[mid] > target){
                right = mid-1;
            }else{//让left不断向后移动达到小于等于target区间的最右边，即右端点，让left等于右端点
                left = mid;
            }
        }
        //不用再进行判断了，因为上面已经进行判断了，如果没有结果就不会到这里
        //到这里就代表右结果，让ret[1]处赋值为left，即右端点坐标
        ret[1] = left;
        return ret;
    }
}

//leetcode:69:x的平方根
class Solution3 {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int n = 0;
        while(left <= right){
            int mid = left+(right - left)/2;
            if((long)mid*mid <= x){
                n = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return n;
    }
}

//leetcode:35：搜索插入的位置
class Solution4 {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid-1;
            }else if(nums[mid] < target){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return left;
    }
}